/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._56_01;

/**
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._56_01
 * @ClassName: SingleNumbers
 * @Author: linyaonan
 * @Date: 2020/4/28 11:42
 */
public class SingleNumbers {

    public static int[] singleNumbers(int[] nums) {
        int p = 0;
        for (int num : nums) {
            p = p ^ num;
        }
        int flag = p & (-p);
        int[] re = new int[2];
        for (int num : nums) {
            if ((flag & num) != 0) {
                re[0] ^= num;
            }
        }
        re[1] = p ^ re[0];
        return re;
    }

    public static void main(String[] args) {
        int[] ints = {1, 1, 2, 3, 3, 4, 4, 6, 5, 5};
        int[] p = singleNumbers(ints);
        System.out.println(p);
    }

}
